
/************************************************
 * Given a nonegtiv integer N, wirte a function f
 * to count how many 1s in 1~N. For example,
 * N = 12, f(N) = 5
 * URL: http://www.msra.cn/Articles/ArticleItem.aspx?Guid=8ae08db5-e059-44bf-9181-83d40a67dadb
 ************************************************/

#include <stdio.h>

/************************************************
 * The simplest method is to emumerate all integers
 * between 1 to N. For each integer, check out its
 * factors. If a factor is equal to 1, increase the
 * counter by 1. This is a O(n^2) algorithm.
 ************************************************/
int ans_1(int N)
{
    int i, j, c = 0;
    for (i = 1; i <= N; i++){
        j = i;
        while ( j != 0 ){
            c += (j % 10 == 1) ? 1 : 0;
            j = j / 10;
        }
    }
    return c;
}

int ans_2(int N)
{
    int r, n, l, h, m, c;

    c = 0;
    r = 1;
    do{
        n = N / (10*r);
        c += n * r;
        l = r;
        h = 2*r-1;
        m = N % (10*r);
        if ( m < l ) c += 0;
        else if ( m > h ) c += r;
        else c += m-l+1;
        r *= 10;
    }while (n != 0);
    return c;
}

int main()
{
	printf("%d\n", ans_2(10));
	return 0;
}